// Copyright (C) Jari Hautio <jari.hautio@iki.fi> 2008. Licensed under GPLv2. See LICENSE.txt in solution folder.
using System;
using System.Collections.Generic;
using System.Text;
using System.Drawing;
using ColorLib;

namespace RyijyApp
{
    public class ColorPicker
    {
        private const double MaxDistanceValue = 4 * 256 * 256;
        private const double MinDistanceValue = -1;

        class ColorItem
        {
            public ColorItem(Color c, double goodnessValue)
            {
                color = c;
                goodness = goodnessValue;
                minColor = c;
                maxColor = c;
            }
            public void Test(Color c, double dist)
            {
                // don't use goodness in min
                if (min > dist)
                {
                    min = dist;
                    minColor = c;
                }
                if (max < dist)
                {
                    max = dist;
                    maxColor = c;
                }
            }
            public double goodness = 0;
            public Color color;
            public Color minColor;
            public Color maxColor;
            public double min = MaxDistanceValue;
            public double max = MinDistanceValue;
            public int count = 0;
        };
        Dictionary<Color, int> hist = new Dictionary<Color, int>(1000);
        List<Color> picked = new List<Color>();
        LinkedList<ColorItem> unpicked = new LinkedList<ColorItem>();
        List<Color> dropped = new List<Color>();
        /// <summary>
        /// Returns list of dropped colors
        /// </summary>
        public List<Color> DroppedColors { get { return dropped; } }
        double diversityFactor = 1.0;
        /// <summary>
        /// Sets color diversity factor. Default is 1.0. Larger values prefer more diverse color selcetions.
        /// Zero uses just color counts.
        /// </summary>
        public double DiversityFactor { get { return diversityFactor; } set { diversityFactor = value; } }
        /// <summary>
        /// Available methods to calculate color distance
        /// </summary>
        public enum DistanceMode { Hue, RGB, UYV, YCbCr,RGBHSV };

        DistanceMode distanceMode = DistanceMode.YCbCr;
        /// <summary>
        /// Gets of sets formula for calculating distance between two colors.
        /// </summary>
        public ColorPicker.DistanceMode ColorDistanceMode { get { return distanceMode; } set { distanceMode = value; } }

        /// <summary>
        /// Constructs new color picker using given color histogram.
        /// </summary>
        /// <param name="colors"></param>
        public ColorPicker(Dictionary<Color, int> colors)
        {
            hist = colors;
            int sum = 0; // sum all histogram values
            // Sort color before adding to unpicked list
            SortedList<int, List<Color>> sorted = new SortedList<int, List<Color>>();
            foreach (KeyValuePair<Color, int> item in colors)
            {
                List<Color> l;
                if (!sorted.TryGetValue(item.Value, out l))
                {
                    l = new List<Color>();
                    sorted.Add(item.Value, l);
                }
                l.Add(item.Key);
                sum += item.Value;
            }
            // Use most used color as reference
            sum = sorted.Count > 0 ? sorted.Keys[sorted.Count-1] : 0;
            foreach (KeyValuePair<int, List<Color>> item in sorted)
                foreach (Color c in item.Value)
                {
                    // initialize goodness value with normalized pixel count
                    // relative to most used color.
                    int cnt = hist[c];
                    ColorItem ci = new ColorItem(c, 1.0*cnt / sum);
                    ci.count = cnt;
                    unpicked.AddLast(ci);
                }
        }

        /// <summary>
        /// Drop rarely used colors with acceptable neighbour color.
        /// Color occurence value are added to best neighbour color.
        /// </summary>
        /// <param name="limit">Colors having at least this many occurences, are not dropped.</param>
        /// <param name="nearestDistance">Closest neighbour color distance must be lower than this to drop a color. Use zero for unlimited distance.</param>
        public void DropColors(int limit, double nearestDistance)
        {
            DropColors(limit, nearestDistance, unpicked.Count);
        }
        /// <summary>
        /// Drop rarely used colors with acceptable neighbour color.
        /// Color occurence value are added to best neighbour color.
        /// </summary>
        /// <param name="limit">Colors having at least this many occurences, are not dropped.</param>
        /// <param name="nearestDistance">Closest neighbour color distance must be lower than this to drop a color. Use zero for unlimited distance.</param>
        /// <param name="count">Maximum number of colors to be dropped.</param>
        public void DropColors(int limit, double nearestDistance, int count)
        {
            if (unpicked.Count == 0 || count == 0) return;
            nearestDistance *= nearestDistance;
            for (LinkedListNode<ColorItem> node = unpicked.First;
                    node != null; )
            {
                if (node.Value.count >= limit)
                {
                    node = node.Next;
                    continue;
                }
                Color color = node.Value.color;
                // Search for target color starting from end
                double dist = MaxDistanceValue;
                ColorItem best = null;
                for (LinkedListNode<ColorItem> trg = unpicked.Last;
                    trg != node; trg = trg.Previous)
                {
                    double d = Distance(color, trg.Value.color);
                    if (d < dist)
                    {
                        dist = d;
                        best = trg.Value;
                    }
                }
                if (best != null &&
                    (nearestDistance == 0 ||
                     nearestDistance >= dist))
                {
                    dropped.Add(color);
                    best.count += node.Value.count;
                    LinkedListNode<ColorItem> oldNode = node;
                    node = node.Next;
                    unpicked.Remove(oldNode);
                    if (--count == 0) return;
                }
                else
                {
                    node = node.Next;
                }

            }
        }

        /// <summary>
        /// Drop rarely used colors with acceptable neighbour color.
        /// Color occurence value are added to best neighbour color.
        /// This is faster version with ColorCube lookup.
        /// </summary>
        /// <param name="limit">Colors having at least this many occurences, are not dropped.</param>
        /// <param name="nearestDistance">Closest neighbour color distance must be lower than this to drop a color. Use zero for unlimited distance.</param>
        /// <param name="count">Maximum number of colors to be dropped.</param>
        public void DropColors2(int limit, double nearestDistance, int count)
        {
            if (unpicked.Count == 0 || count == 0) return;
            // Use color cube for fast color lookups
			GenericColorCube<ColorItem> cc = new GenericColorCube<ColorItem>();
            foreach (ColorItem n in unpicked)
                cc.Add(n.color, n);

            nearestDistance *= nearestDistance;
            for (LinkedListNode<ColorItem> node = unpicked.First;
                    node != null; )
            {
                if (node.Value.count >= limit)
                {
                    node = node.Next;
                    continue;
                }
                Color color = node.Value.color;
                // Search for target color in nearest colors in color space
                cc.Remove(color);
                Dictionary<Color,ColorItem> candidates = cc.FindMore(color, 1);
                double dist = MaxDistanceValue;
                ColorItem best = null;
                foreach (KeyValuePair<Color,ColorItem> c in candidates)
                {
                    double d = Distance(color, c.Key);
                    if (d < dist)
                    {
                        dist = d;
                        best = c.Value;
                    }
                }
                if (best != null &&
                    (nearestDistance == 0 ||
                     nearestDistance >= dist))
                {
                    dropped.Add(color);

                    best.count += node.Value.count;
                    LinkedListNode<ColorItem> oldNode = node;
                    node = node.Next;
                    unpicked.Remove(oldNode);
                    if (--count == 0) return;
                }
                else // could not remove
                {
                    // no need to put back to cube, because this is too far from other colors
                    node = node.Next;
                }

            }
        }

        /// <summary>
        /// Picks n best colors and returns picked colors.
        /// </summary>
        /// <param name="n">number of colors to pick</param>
        /// <returns>Picked color list</returns>
        public List<Color> PickColors(int n)
        {
            // if unpicked list is already ok, then just use it.
            if (unpicked.Count <= n)
            {
                PickAllUnpicked();
            }
            else
            {
                for (int i = 0; i < n; i++)
                    Pick();
            }
            return picked;
        }

        /// <summary>
        /// Just move all colors from unpicked to picked list.
        /// </summary>
        private void PickAllUnpicked()
        {
            for( LinkedListNode<ColorItem> c = unpicked.Last;
                c != null;
                c = c.Previous)
            {
                picked.Add(c.Value.color);
            }
            unpicked.Clear();
        }
        public Color Pick()
        {
            if (picked.Count == 0)
            {
                return PickPopular();
            }
            else if (picked.Count > 4)
            {
                return PickDiverse( 0.75f+0.25f*(picked.Count % 3) );
            }
            else return PickDiverse(1.0f+ 0.5f*4.0f/picked.Count);
        }
        /// <summary>
        /// Pick most popular color
        /// </summary>
        /// <returns></returns>
        Color PickPopular()
        {
            Color c = unpicked.Last.Value.color;
            picked.Add(c);
            unpicked.RemoveLast();
            // Update cache added
            UpdateDistances(c);
            return c;
        }

        /// <summary>
        /// Calculate distance between two colors.
        /// </summary>
        /// <param name="c1">First color</param>
        /// <param name="c2">Second color</param>
        /// <returns>Squared distance between the colors</returns>
        double Distance(Color c1, Color c2)
        {
            switch (distanceMode)
            {
                case DistanceMode.Hue: return ColorMath.DistanceHue(c1,c2);
                case DistanceMode.RGB: return ColorMath.DistanceRGB(c1, c2);
                case DistanceMode.UYV: return ColorMath.DistanceUYV(c1, c2);
                case DistanceMode.YCbCr: return ColorMath.DistanceYCbCr(c1, c2);
                case DistanceMode.RGBHSV: return ColorMath.DistanceRGBHSV(c1, c2);
                default: return ColorMath.DistanceRGB(c1, c2);
            }
        }
        // Old version without caching
        Color PickDiverseNoCache(float prefer)
        {
            LinkedListNode<ColorItem> best = null;
            double dist = MinDistanceValue;
            for (LinkedListNode<ColorItem> n = unpicked.Last;
                n != null; n = n.Previous)
            {
                Color c1 = n.Value.color;
                double dmin = MaxDistanceValue;
                // find distance to closest picked color
                foreach (Color c2 in picked)
                {
                    double d = Distance(c1, c2);
                    if (d < dmin) dmin = d;
                }
                if (dmin > dist)
                {
                    dist = dmin;
                    best = n;
                }
            }
            if (best != null)
            {
                picked.Add(best.Value.color);
                unpicked.Remove(best);
                // dont update cacahe here, because
                // this serves only as reference implementation
                return best.Value.color;
            }
            return Color.Empty;
        }
        /// <summary>
        /// Picks best avaialble color from unpicked colors.
        /// Cached version
        /// </summary>
        /// <param name="preferPopular">Factor for prefering popular colors</param>
        Color PickDiverse(float preferPopular)
        {
            LinkedListNode<ColorItem> best = null;
            double dist = MinDistanceValue;
            for (LinkedListNode<ColorItem> n = unpicked.Last;
                n != null; n = n.Previous)
            {

                // list items already contain min and max values
                double d = diversityFactor*n.Value.min + 10000* preferPopular * n.Value.goodness;

                if (dist < d)
                {
                    dist = d;
                    best = n;
                }
            }
            if (best != null)
            {
                ColorItem ci = best.Value;
                picked.Add(ci.color);
                unpicked.Remove(best);
                UpdateDistances(ci.color);
                return ci.color;
            }
            return Color.Empty;
        }
        /// <summary>
        /// Updates cached distace values in unpicked with given color
        /// </summary>
        /// <param name="c1"></param>
        void UpdateDistances(Color c1)
        {
            // update distance values with newly picked item
            for (LinkedListNode<ColorItem> n = unpicked.First;
                n != null; n = n.Next)
            {
                double d = Distance(n.Value.color, c1);
                n.Value.Test(c1, d);
            }
        }
        // noncached version
        public Dictionary<Color, Color> GetColorMap_()
        {
            Dictionary<Color, Color> colorMap = new Dictionary<Color, Color>();

            foreach (ColorItem ci in unpicked)
            {
                Color c1 = ci.color;
                Color best = Color.Black;
                double dist = MaxDistanceValue;

                foreach (Color c2 in picked)
                {
                    double d = Distance(c1, c2);
                    if (d < dist)
                    {
                        dist = d;
                        best = c2;
                        if (dist == 0) break;
                    }
                }
                colorMap.Add(c1, best);
            }
            foreach (Color c1 in dropped)
            {
                Color best = Color.Black;
                double dist = MaxDistanceValue;

                foreach (Color c2 in picked)
                {
                    double d = Distance(c1, c2);
                    if (d < dist)
                    {
                        dist = d;
                        best = c2;
                        if (dist == 0) break;
                    }
                }
                colorMap.Add(c1, best);
            }
            return colorMap;
        }

        /// <summary>
        /// Gets a color map for converting unpicked colors to best picked colors
        /// </summary>
        /// <returns></returns>
        public Dictionary<Color, Color> GetColorMap()
        {
            Dictionary<Color, Color> colorMap = new Dictionary<Color, Color>();

            foreach (ColorItem ci in unpicked)
            {
                colorMap.Add(ci.color, ci.minColor);
            }

            ColorCube cc = null;
            // Use color cube for fast color lookups if more than 64 colors is selected
            if (picked.Count > 64)
            {
                cc = new ColorCube();
                foreach (Color c in picked)
                    cc.Add(c);
            }

            foreach (Color c1 in dropped)
            {
                Color best = Color.Black;
                double dist = MaxDistanceValue;

                List<Color> colors = picked;
                if (cc!= null)
                {
                    colors = new List<Color>();
                    colors.AddRange( cc.FindMore(c1, 2).Keys );
                }

                foreach (Color c2 in colors)
                {
                    double d = Distance(c1, c2);
                    if (d < dist)
                    {
                        dist = d;
                        best = c2;
                        if (dist == 0) break;
                    }
                }
                colorMap.Add(c1, best);
            }
            return colorMap;
        }
    }
}
